package com.review.dp;

public class a_2 {
    //https://www.bilibili.com/video/BV12W411v7rd
    //组合=sum
    private boolean dp(int[] arr, int sum) {
        return subset(arr, arr.length - 1, sum);
    }

    private boolean subset(int[] arr, int i, int sum) {
        // i代表选不选下标为i的数
        if (sum == 0) {
            return true;
        } else if (i == 0) {
            return arr[i] == sum;
        } else if (arr[i] > sum) {
            return subset(arr, i - 1, sum);
        } else {
            return subset(arr, i - 1, sum) || subset(arr, i - 1, sum - arr[i]);
        }
    }

    public static void main(String[] args) {
        System.out.println(new a_2().dp(new int[]{1, 2, 3, 4, 12, 7, 5}, 11));
    }
}
